package demo1;

public class MyLinkedList {
    static class ListNode{
         int data;
         ListNode next; //指向下一个节点
         ListNode prev;//指向前一个节点

        public ListNode(int data) {
            this.data = data;
        }
    }
//在链表的实现中，没有usedsize这个属性
    ListNode head; //创建指向头节点的指针
    ListNode last ;  //创建指向尾结点的指针
  //头插法
         public void addFirst(int data){
             //双向链表的头插
            //两种情况：1 头结点为空，2.头结点不为空、
             ListNode cur = new ListNode(data);
             if(head ==null){
                 last = head = cur;
             }else {
                 //如果头结点不为空
                 cur.next = head;
                 head.prev = cur;
                 head = cur;
             }
         }
        //尾插法
         public void addLast(int data){
             //先找到尾结点
            ListNode cur = new ListNode(data);
             if(head == null){
                 last = head = cur;
                 return;
             }
          //有了last指针，便不再需要遍历链表了
             //如果链表不为空：
             last.next = cur;
             cur.prev = last;
             last  = cur;
         }
  //任意位置插入,第一个数据节点为0号下标
         public void addIndex(int index,int data){
             //先判断index值是否合法
             if(index<0||index>size()){
                 System.out.println("index值不合法");
                 return;
             }

             if(index ==0){
                 addFirst(data);
                 return;
             }
             if(index ==size()){
                 addLast(data);
                 return ;
             }
             if(index>0&&index<size()){
                   //中间插入
                 ListNode cur = head;
                 while(index>0){
                     //先找到cur位置
                     cur =cur.next;
                     index--;
                 }
                 ListNode curN = new ListNode(data);
                 //将插入的节点与左右两边的节点相连
                 curN.next = cur;
                 curN.prev = cur.prev;
                 curN.prev.next = curN;
                 cur.prev = curN;

                    return ;
             }
         }
  //查找是否包含关键字key是否在双链表当中
         public boolean contains(int key){
             //判断关键字key是否在双链表中
             ListNode cur = head;

             while (cur!=null){
                 if(cur.data == key){
                     return  true;
                 }
                 cur =cur.next;
             }
             return  false;
         }
  //删除第一次出现关键字为key的节点
         public void remove(int key) {
             //删除第一个出现关键字key的节点，
             //删除头结点，尾结点，中间节点的过程是不一样的。
             //先判断出现此节点的位置
             //判断关键字key是否在双链表中
             ListNode cur = head;
             while (cur != null) {
                 if (cur.data == key) {
                     //需要判断此节点是什么节点
                     if (cur == head) {
                         cur.next.prev = cur.prev;
                         head = head.next;
                         return;
                     } else {
                         cur.prev.next = cur.next;
                         if (cur == last) {
                             last = last.prev;
                             return;
                         } else {
                             cur.next.prev = cur.prev;
                             return;
                         }
                     }
                 }
                 cur = cur.next;
             }
         }
  //删除所有值为key的节点
          public void removeAllKey(int key) {
              ListNode cur = head;

              while (cur != null) {
                  if (cur.data == key) {
                      //需要判断此节点是什么节点
                      if (cur == head) {
                          cur.next.prev = cur.prev;
                          head = head.next;
                      }else {
                          cur.prev.next = cur.next;
                          if(cur ==last){
                              last =last.prev;
                          }else {
                              cur.next.prev = cur.prev;
                          }
                      }
                  }
                  cur =cur .next;
              }
          }
  //得到双链表的长度
         public int size(){
             ListNode cur = head;
             int count = 0;
             while (cur !=null){
                 count++;
                 cur = cur.next;
             }
             return count;
         }
        public void display(){
             //展示链表中所有的内容
             ListNode cur = head;
             while (cur!=null){
                 System.out.print(cur.data+  "  ");
                 cur =cur.next;
             }
        }
         public void clear(){
            //将链表置为空
             //将链表置为空是指，链表中所有的节点均没有引用指向
             ListNode cur = head;
             while(cur !=null){
                 ListNode curN = cur.next;
                 cur.prev = null;  //是将当前节点中的两个指针域置为空，此时cur.prev是本指针置为空，而不是cur.prev指向的节点为空
                                          //要用辩证思维看待，而不是形式逻辑
                 cur.next = null;
                 cur =curN;
             }
            //当遍历完毕后，头结点与尾节点还有引用指向
             //引用包括临时变量，也包括节点中指针
            head = last = null;
    }
}
